package main

import "fmt"

/**
Invert a binary tree.

Example:

Input:

     4
   /   \
  2     7
 / \   / \
1   3 6   9
Output:

     4
   /   \
  7     2
 / \   / \
9   6 3   1


分治法

翻转二叉树等于把每一个结点的左右结点翻转
*/

type TreeNode struct {
	Val   int
	Left  *TreeNode
	Right *TreeNode
}

/*
*
翻转一棵树 = 翻转左右子树 + 交换左右子树

left/right 已经是翻转后的子树
你只需要把它们换一下位置即可
更符合“先处理子问题，再合并结果”的递归思维

对树的典型步骤就是：
递归解决左子树的问题
递归解决右子树的问题
把左右子树的结果合并（交换、判断、累加等）
*/
func invertTree(root *TreeNode) *TreeNode {
	if root == nil {
		return root
	}

	left := invertTree(root.Left)
	right := invertTree(root.Right)
	root.Left = right
	root.Right = left
	return root
}

func main() {
	fmt.Println(3 / 2)
	a := &TreeNode{Val: 2, Left: nil, Right: nil}
	b := &TreeNode{Val: 3, Left: nil, Right: nil}
	root := &TreeNode{Val: 1, Left: a, Right: b}
	fmt.Println(invertTree(root))

}

func invertTree(root *TreeNode) *TreeNode {
	if root == nil {
		return root
	}
	left := invertTree(root.Left)
	right := invertTree(root.Right)
	root.Left = right
	root.Right = left
	return root
}
